#include <cstdint>
#include <vector>

using namespace std;

class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        vector<int64_t> dp(1 << hats.size());
        vector<vector<int>> hats_to_persion(41);
        for (int i = 0; i < hats.size(); i++) {
            for (int& hat : hats[i]) {
                hats_to_persion[hat].emplace_back(i);
            }
        }
        dp[0] = 1;
        for (int i = 1; i < 41; i++) {
            vector<int64_t> ndp(dp);
            for (int j = (1 << hats.size()) - 1; j >= 0; j--) {
                for (int& person : hats_to_persion[i]) {
                    if (j & (1 << person)) {
                        continue;
                    }
                    int nxt = j + (1 << person);
                    ndp[nxt] += dp[j];
                    ndp[nxt] %= (int64_t) (1e9 + 7);
                }
            }
            swap(dp, ndp);
        }
        return dp.back();
    }
};